package algorithm;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.Iterator;
import java.util.List;

public class Combination {

	private Object[] arrayObj;// objects of C{M}

	private int n;// C{M,N}

	List<int[]> ciList = new ArrayList<int[]>();

	List<Object[]> cList;

	public Combination(Object[] array, int n) {
		if (array == null || array.length < n)
			throw new IllegalArgumentException("Input Error: m < n");
		this.arrayObj = array;
		this.n = n;
	}

	public void doCombination() {
		mn(arrayObj.length, n);
	}

	public void printCombination() {
		for (Iterator<int[]> iter = ciList.iterator(); iter.hasNext();) {
			StringBuffer sb = new StringBuffer();
			int[] cIdx = iter.next();
			for (int i = 0; i < cIdx.length; i++) {
				sb.append(arrayObj[cIdx[i] - 1]).append(",");
			}
			sb.setLength(sb.length() - 1);
			System.out.println(sb);
		}
	}

	public List<Object[]> getCombination() {
		cList = new ArrayList<Object[]>();
		for (Iterator<int[]> iter = ciList.iterator(); iter.hasNext();) {
			int[] cIdx = iter.next();
			Object[] c = new Object[cIdx.length];
			for (int i = 0; i < cIdx.length; i++) {
				c[i] = arrayObj[cIdx[i] - 1];
			}
			cList.add(c);
		}
		return cList;
	}

	private void mn(int m, int n) {
		if (m < n)
			throw new IllegalArgumentException("Error   m   <   n");
		int[] array = new int[m];
		for (int i = 0; i < m; i++)
			array[i] = i + 1;
		BitSet bs = new BitSet(m);
		for (int i = 0; i < n; i++)
			bs.set(i, true);
		do {
			addItems(array, bs);
		} while (moveNext(bs, m));

	}

	private boolean moveNext(BitSet bs, int m) {
		int start = -1;
		while (start < m)
			if (bs.get(++start))
				break;
		if (start >= m)
			return false;

		int end = start;
		while (end < m)
			if (!bs.get(++end))
				break;
		if (end >= m)
			return false;
		for (int i = start; i < end; i++)
			bs.set(i, false);
		for (int i = 0; i < end - start - 1; i++)
			bs.set(i);
		bs.set(end);
		return true;
	}

	private void addItems(int[] array, BitSet bs) {
		int[] cIndexes = new int[n];
		int j = 0;
		for (int i = 0; i < array.length; i++) {
			if (bs.get(i)) {
				cIndexes[j] = array[i];
				j++;
			}
		}
		ciList.add(cIndexes);
	}

	private void printAll(int[] array, BitSet bs) {
		StringBuffer sb = new StringBuffer();
		for (int i = 0; i < array.length; i++)
			if (bs.get(i))
				sb.append(array[i]).append(',');
		sb.setLength(sb.length() - 1);
		System.out.println(sb);
	}

	public static void main(String[] args) throws Exception {
		Integer[] arrays = new Integer[12];
		for (int i = 0; i < arrays.length; i++) {
			arrays[i] = i + 1 ;
		}
		Combination c = new Combination(arrays, 6);
		c.doCombination();
		System.out.println(c.getCombination().size());
//		c.printCombination();
	}
}
